Lúc đầu được Michael Blake viết dưới dạng một spec script (kịch bản được viết mà không được đặt trước hay mua, với hy vọng rằng nó sẽ được bán), kịch bản không bán được vào giữa những năm 1980.[5] Đầu năm 1986 (khi còn tương đối vô danh), chính Kevin Costner là người động viên Blake biến kịch bản thành tiểu thuyết, để nó có cơ may được chuyển thể thành phim hơn. Bản viết tay cuốn tiểu thuyết Dances with Wolves bị nhiều nhà xuất bản từ chối nhưng cuối cùng cũng được xuất bản thành sách bìa mềm vào năm 1988. Là tiểu thuyết, bản quyền được Costner mua và nhắm tới chiếc ghế đạo diễn. Quá trình sản xuất thực tế kéo dài bốn tháng, từ 18 tháng 7 đến 23 tháng 11 năm 1989. Bộ phim được quay hầu hết tại Nam Dakota, chủ yếu gần Pierre và Rapid City, với một vài cảnh được quay tại Wyoming; các địa điểm quay cụ thể gồm có Công viên quốc gia Badlands, Black Hills, Vùng hoang dã Sage Creek, khu vực Sông Belle Fourche.[6] Các cảnh săn trâu này được quay tại trại trâu Triple U, bên ngoài Fort Pierre, Nam Dakota, cũng giống như các phân cảnh ở Fort Sedegwick.[7]

Quá trình sản xuất bị trì hoãn nhiều lần do thời tiết thất thường tại Nam Dakota, do khó khăn trong việc "đạo diễn" những con sói khó bảo, và sự phức tạp của những cảnh chiến đấu của những thổ dân da đỏ. Khó nhất là trường đoạn săn trâu đặc sắc của bộ phim: cuộc săn đuổi phức tạp này được quay suốt ba tuần sử dụng 100 thổ dân da đỏ và một đàn trâu vài trăm con chạy tán loạn. Trong một cảnh, Costner (người tự thực hiện hầu hết tất cả những cảnh trên lưng ngựa của mình) bị một người cưỡi ngựa khác chắn ngang và bị văng khỏi lưng ngựa, suýt gãy lưng. Tai nạn này được lưu lại trong The Creation of an Epic, bộ phim tài liệu sau hậu trường có trong DVD ấn bản đặc biệt của phim.[8] Theo bộ phim tài liệu này, không có con trâu nào được tạo ra bằng máy tính (CGI khi ấy còn mới sơ khai) và chỉ một vài con là trâu điện tử được chế tạo bằng máy. Thật ra, Costner và ê kíp đã thuê trại trâu lớn nhất nước, với hai trong số những con trâu được thuần hóa này được mượn từ ca sĩ Neil Young;[9] đây là đàn trâu được sử dụng cho trường đoạn săn trâu.

Kinh phí vượt dự toán là điều không thể tránh khỏi, do Costner phá vỡ vài "quy luật" ngầm của Hollywood dành cho những người mới lần đầu làm đạo diễn: càng tránh quay ở ngoài trời và tránh làm việc với trẻ con và động vật càng tốt. Kết quả là cuối quá trình sản xuất, Costner buộc phải lấy tiền túi 3 triệu USD bổ sung cho kinh phí ban đầu 15 triệu USD của bộ phim.[10] So với sự thất bại đình đám của Heaven’s Gate năm 1980 của Michael Cimino, được xem là bộ phim Viễn Tây được quản lý tồi nhất trong lịch sử điện ảnh, thì dự án của Costner bị gán cho cái tên "Kevin’s Gate" một cách châm biếm bởi các phê bình Hollywood và những chuyên gia hoài nghi về một bộ phim Viễn Tây có phụ đề một phần và dài ba tiếng của một nhà làm phim mới vào nghề.[5]

Ngôn ngữ được nói trong phim là một phiên bản khá chính xác, dù đã được đơn giản hóa, của ngôn ngữ Loakota thực sự. Doris Leader Charge, thầy giáo dạy ngôn ngữ Lakota Sioux năm đó đã 60 tuổi, là người huấn luyện diễn thoại bằng tiếng Lakota trên phim trường và còn đóng vai Pretty Shield, vợ của Tù trưởng Ten Bears,[5] do Floyd Red Crow Westerman đóng.